package com.xyj.week04;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author GuXiaoYao
 * @version 1.0.0
 * @since 2021/9/7
 * "abcdxabcde"
 * "abcdeabcdx"
 */
public class T3 {

    public static void main(String[] args) {
        System.out.println(findAnagrams("abab", "ab"));
    }
        public static List<Integer> findAnagrams(String s, String p) {
            List<Integer> availableList= new ArrayList<>();
            //一个有效的  一个窗口的Map
            Map<Character,Integer> availableMap=new HashMap<>();
            Map<Character,Integer> windowMap=new HashMap<>();
            //将p字符串放入Map中
            char [] avalibleChars=p.toCharArray();
            char [] allChars=s.toCharArray();
            for(char c:avalibleChars){
                availableMap.put(c,availableMap.getOrDefault(c,0)+1);
            }
            int left=0,right=0,flag=0;

            while(right<allChars.length){
                //右窗口移动
                char cur=allChars[right];
                right++;
                if(availableMap.containsKey(cur)){
                    windowMap.put(cur,windowMap.getOrDefault(cur,0)+1);
                    if(windowMap.get(cur).equals(availableMap.get(cur))){
                        //如果达到有效值了
                        flag++;
                    }
                }
                while(right-left==p.length()) {
                    //如果刚好达到p的长度，就开始判断当前flag是不是等于有效的长度
                    if(availableMap.size()==flag){
                        availableList.add(left);
                    }
                    char leftChar=allChars[left];
                    left++;
                    //判断flag是否要变 并且维护windowMap
                    if(availableMap.containsKey(leftChar)){
                        if(windowMap.get(leftChar).equals(availableMap.get(leftChar))){
                            //如果达到有效值了
                            flag--;
                        }
                        windowMap.put(leftChar,windowMap.get(leftChar)-1);
                    }
                }
            }
            return availableList;
        }
}
